package week7.util;

import java.util.ArrayList;
import java.util.List;

public abstract class SortedList<Elem> implements SortedSet<Elem> {

	//-------------------------------------------Private Variabelen--------------------------------
	
	/**
	 * De lijst welke de objecten zal bevatten.
	 */
	private List<Elem> _lijst = new ArrayList<Elem>();
	
	//-------------------------------------------Queries-------------------------------------------

	/**
	 * {@inheritDoc}
	 */
	@Override
	public boolean contains(Elem elem) {
		return _lijst.contains(elem);
	}
	
	/**
	 * {@inheritDoc}
	 */
	@Override
	public Elem get(int index) {
		return _lijst.get(index);
	}
	
	/**
	 * Levert de lijst van alle objecten op.
	 */
	protected List<Elem> getList() {
		return _lijst;
	}
	
	/**
     * Zoekt naar een object in deze <tt>SortedList</tt>.
     * Levert de index op van het eerste element dat 
     * minstens 'zo groot' is als het gezochte getal.
     * @param val gezochte getal
     * @return index van het eerste element dat niet 'kleiner' is 
     * dan <tt>element</tt>; <br>
     * <tt>this.size()</tt> als alle elementen kleiner zijn 
     * dan <tt>element</tt>
     * @ensure <tt>0 <= result && result <= size() &&
     *             lessThan(get(0 .. result-1), element) && 
     *             !lessThan(element, get(result .. size()-1))</tt>
     */
	private int itemIndex(Elem element) {
		// Filter de mogelijkheden die er net buiten vallen eruit.
        if(_lijst.size() == 0 || !lessThan(_lijst.get(0), element))
        	return 0;			// Kleiner dan of gelijk aan de kleinste
        
        int ondergrens = 0;			   // Laagst mogelijke index
        int bovengrens = _lijst.size(); // Hoogst mogelijke index (groter dan de hele lijst)
        
        // lijst.get(ondergrens) < val <= lijst.get(bovengrens+1)
		while (ondergrens < bovengrens) {
			int midden = ondergrens + (bovengrens - ondergrens) / 2; // Voorkom overflow van ondergrens + bovengrens
			if (!lessThan(_lijst.get(midden), element)) {	// Gezochte waarde zit boven midden
				bovengrens = midden;
			} else {						// Gezochte waarde zit onder midden
				ondergrens = midden + 1;
			}
		}
		
        return ondergrens;
	}
	
	/**
	 * {@inheritDoc}
	 */
	@Override
	public int size() {
		return _lijst.size();
	}
	
	//-------------------------------------------Commands------------------------------------------
	
	/**
	 * {@inheritDoc}
	 */
	@Override
	public boolean add(Elem elem) {
		// Vind de return waarde
		boolean result = !contains(elem);
		
		// Voeg het element toe op de gevonden index
		if(result) {
			_lijst.add(itemIndex(elem), elem);
		}
		
		// Geef het resultaat terug
		return result;
	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public boolean remove(Elem elem) {
		return _lijst.remove(elem);
	}
	
	//-------------------------------------------Abstracts-----------------------------------------
	
	/**
	 * {@inheritDoc}
	 */
	@Override
	public abstract boolean lessThan(Elem e1, Elem e2);
}
